package com.daji.search_and_sort;

import java.util.Arrays;

/*
 * 堆是一颗完全二叉树,且必须保证
 * 堆排序的前置知识是选择排序。
 * 大根堆和小根堆：
 * 大根堆的每个父节点一定比子结点大。比如 [3,2,1] 是一个大根堆，[ 3.1,2 ] 也是一个大根堆。与此相反的定义就是小根堆
 * 
 * 堆排序利用的性质：
 * 完全二叉树性质（假设数组第一个下标为0）：
 * 1、总长度/2 - 1 = 第一个非叶结点（如果数组第一个下标为1,计算结果就是总长度/2）
 * 2、结点的左子结点坐标 = 结点坐标×2 -1 （如果数组第一个下标是0）
 *
 * 堆排序注意事项：
 * 1、如果升序，用大顶堆,如果降序，用小顶堆
 * （很好理解，因为大顶堆构建的有序数组，是把堆顶元素逐步下沉得到的，
 * 执行过程类似选择排序，循环将最大值沉到数组尾，最后得到的是一个升序数组）
 *
 * 2、平均时间复杂度：O(nlogn)
 *    最佳时间复杂度：O(nlogn)
 *    最差时间复杂度：O(nlogn)
 *    稳定性：不稳定
 * */

//大顶堆 ———— 升序
public class HeapSort {
    public static void main(String[] args) {
        //这个arr数组，针对堆而言，其实就是按照【层序插入】的【完全二叉树】
        //这个arr数组，针对堆而言，其实就是按照【层序插入】的【完全二叉树】
        //这个arr数组，针对堆而言，其实就是按照【层序插入】的【完全二叉树】
        int[] arr = {7, 6, 12, 11, 5, 12, 0, 3, 7, 20};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        //1.构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {//遍历条件利用了完全二叉树性质：总长度/2 - 1 = 第一个非叶结点
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }
        //这一步完事后大根堆就构建完了。
        //2.调整堆结构+交换堆顶元素与末尾元素
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr, 0, j);//将堆顶元素与末尾元素进行交换 (排出了最大值，沉到了数组尾部)
            // [重要]这里执行adjustHeap为什么不用再套一层for循环？就像上面的例子一样
            // 原因是，除了堆顶节点，其他的子节点已经是一个大根堆的结构了，自然不需要对它们调整。
            // adjustHeap(arr, 0, j) 的第二个参数始终是0.因为交换后，堆顶结点无序，肯定不符合大根堆结构，
            // 与此同时，除了堆顶结点不符合大根堆，其它结点全部都符合大根堆。所以我们只需要调整一次堆顶结点即可
            // adjustHeap(arr, 0, j) 的第三个参数j，每次递减，是正确的。每经历一次循环，就会将现有最大元素下沉到堆的最尾部。
            adjustHeap(arr, 0, j);//重新对堆进行调整
            //这个执行过程类似选择排序，不停将最大值沉到数组尾，最后得到的是一个升序数组
        }

    }

    /**
     * 构建和调整大顶堆
     *
     * @param arr
     * @param fatherIndex
     * @param length
     */
    public static void adjustHeap(int[] arr, int fatherIndex, int length) {
        int temp = arr[fatherIndex];//先取出父结点的值
        //下面的for的第一个参数（sonIndex=fatherIndex*2+1），利用了完全二叉树性质：结点的左子结点坐标 = 结点坐标×2 -1 （如果数组第一个下标是0）
        //那for的第三个参数（sonIndex=sonIndex*2+1）是为了什么呢？是为了递归构建结点的左子结点，结点的左子结点的左子结点.....
        //因为一旦调整了“中间层”的结点，那他下面的左子结点仍然需要调整。即使他下面的左子节点调整过一遍。
        for (int sonIndex = fatherIndex * 2 + 1; sonIndex < length; sonIndex = sonIndex * 2 + 1) {//从i结点的左子结点开始，也就是2i+1处开始 (i从0开始取)
            //sonIndex + 1 < length 是为了针对只有一个叶结点的情况。如果不加这个校验，arr[sonIndex+1]会报indexOutOfBound错误
            //这个if在前面，因为在比较父子之前，应该先比较两个儿子谁大。
            if (sonIndex + 1 < length && arr[sonIndex] < arr[sonIndex + 1]) {//如果左子结点小于右子结点，sonIndex指向右子结点
                sonIndex++;
            }
            if (arr[sonIndex] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[fatherIndex] = arr[sonIndex];
                fatherIndex = sonIndex;  //为了将sonIndex变量带出for循环
            } else {
                break;
            }
        }
        //如果是构建多层大顶堆，最终也只需要交换一次。所以可以将交换的的动作放在for循环外面。
        arr[fatherIndex] = temp;//将temp值放到最终的位置（也就是彻底完成父子节点置换操作）
    }

    //交换堆顶和堆尾元素
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}